package org.example;

//class UnionFind {
//    private final int[] father;
//
//    UnionFind(int n) {
//        father = new int[n + 1];
//        for (int i = 1; i < n + 1; i++) {
//            father[i] = i;
//        }
//    }
//
//    private int find(int u) {
//        if (father[u] == u) {
//            return u;
//        }
//        father[u] = find(father[u]);
//        return father[u];
//    }
//
//    private boolean isSame(int u, int v) {
//        return find(u) == find(v);
//    }
//
//    public boolean join(int u, int v) {
//        u = find(u);
//        v = find(v);
//        if (u == v) {
//            return true;
//        }
//        father[v] = u;
//        return false;
//    }
//
//}
//
//class Solution {
//    public int[] findRedundantConnection(int[][] edges) {
//        int n = edges.length;
//        UnionFind unionFind = new UnionFind(n);
//        for (int[] edge : edges) {
//            int u = edge[0], v = edge[1];
//            if (unionFind.join(u, v)) {
//                return edge;
//            }
//        }
//        return null;
//    }
//}

//二刷
class UnionFind {
    int[] father;
    UnionFind(int n) {
        father = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
        }
    }

    int find(int i) {
        if (father[i] == i) {
            return i;
        }
        father[i] = find(father[i]);
        return father[i];
    }

    boolean tryJoin(int i, int j) {
        i = find(i);
        j = find(j);
        if (i == j) {
            return false;
        }
        father[j] = i;
        return true;
    }
}

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind unionFind = new UnionFind(n);
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            if (!unionFind.tryJoin(u, v)) {
                return edge;
            }
        }
        return null;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}